# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-03-31 15:10:31
# @Last Modified by:   bao
# @Last Modified time: 2017-05-15 20:49:58
import sys
import os
import re
import copy
import random
import networkx as nx
from datetime import datetime
sys.path.append("..")

try:
    from CoreSim.SchedulerFair import *
    from CoreSim.Flow import *
    from CoreSim.Event import *
    from CoreSim.Link import *
    from CoreSim.Unit import *
    from Controller.gen_topo_fully import *
except:
    raise


def get_weight(weight):
    integral = int(weight)
    fractional = weight - integral
    if not integral:
        return 1
    else:
        if fractional < 0.5:
            return integral
        else:
            return integral + 1


class MScheduler(SchedulerFair):
    """Multicast scheduler"""

    def __init__(self, topo_args, flow_args, conf_args):
        SchedulerFair.__init__(self)
        self.type = 'null'

        # topology
        self.numHosts = topo_args[0]
        self.numToRs = topo_args[1]
        self.numCores = topo_args[2]
        self.numOCSes = topo_args[3]
        self.link_sh_Bw = topo_args[4]
        self.link_ss_Bw = topo_args[5]
        self.mflowsFileName = flow_args[0]
        self.uflowsFileName = flow_args[1]
        self.workload = flow_args[2]

        self.com_network = nx.DiGraph()  # logically topology (srcNodeId, dstNodeId)
        self.s_matches = {}  # static pre_matches
        self.d_matches = {}  # dynamic pre_matches

        self.ucastToR = {}  # ToRId: ([srcPort1, ..., srcPortN], [dstPort1, ..., dstPortN])
        self.ucastPort = {}  # PortId: ([srcToRId1, ..., srcToRIdN], [dstToRId1, ..., dstToRId2])
        self.ucastToRFully = {}  # ToRId: ([srcPort1, ..., srcPortN], [dstPort1, ..., dstPortN])
        self.ucastPortFully = {}  # PortId: ([srcToRId1, ..., srcToRIdN], [dstToRId1, ..., dstToRId2])

        # routing
        # path is identified by source node ID and destination node ID
        # multi-paths [[id1, id2, id3],...,[id1, id2, id3]]
        self.k = self.numCores
        self.pathLinkIdList = {}

        # flows
        self.mcastFlows = {}  # Initial multicast flows
        self.runningFlowsDict = {}

        # reconfiguration
        self.interval = conf_args[0]  # reconfiguration interval
        self.adjust_delay = conf_args[1]  # reconfiguration delay
        self.update_enable = conf_args[2]
        self.time_threshold = 100000
        self.host_location = {}
        self.UpdateTopologyEvent = 0
        self.LinkAdjustedEvent = 0

    def AssignUnicast(self, eventQueue):
        """
        initial unicast flows
        """
        f = open(inDir + self.uflowsFileName, "r")
        for line in f.readlines():
            l = line.split()
            flow = Flow()
            flow.flowId = len(self.flows) + 1
            flow.startId = int(l[0])
            flow.endId = int(l[1])
            flow.startTime = float(l[2])
            flow.SetFlowSize(float(l[3]) * 8)
            self.flows.append(flow)

            event = FlowArrivalEvent(flow.startTime, flow)
            eventQueue.push(event, event.time)
        f.close()

    def InitialTopology(self, topoFileName):
        """
        Physically topology: Links
        Logically topology: com_network, mid_network
        """

        # 1. Add links between Hosts and ToRs
        for hostId in xrange(1, self.numHosts * self.numToRs + 1):
            torId = (hostId - 1) / self.numHosts + 1
            self.host_location[hostId] = torId
            torNodeId = ConvertToNodeId(torId, ToR, self.numHosts * self.numToRs, self.numToRs)
            links2t = Link((hostId, torNodeId), self.link_sh_Bw)
            linkt2s = Link((torNodeId, hostId), self.link_sh_Bw)

            self.Links[hostId, torNodeId] = links2t
            self.Links[torNodeId, hostId] = linkt2s
            self.H2SLinks[hostId, torNodeId] = links2t  # demand_estimation
            self.H2SLinks[torNodeId, hostId] = linkt2s  # demand_estimation

        # 2. Add links between Cores and ToRs
        for torId in xrange(1, self.numToRs + 1):
            torNodeId = ConvertToNodeId(torId, ToR, self.numHosts * self.numToRs, self.numToRs)
            for coreId in xrange(1, self.numCores + 1):
                coreNodeId = ConvertToNodeId(coreId, Core, self.numHosts * self.numToRs, self.numToRs)
                self.Links[torNodeId, coreNodeId] = Link((torNodeId, coreNodeId), self.link_ss_Bw)
                self.Links[coreNodeId, torNodeId] = Link((coreNodeId, torNodeId), self.link_ss_Bw)
                self.com_network.add_edge(torNodeId, coreNodeId)
                self.com_network.add_edge(coreNodeId, torNodeId)
                # print torNodeId, coreNodeId

        # 3. Add links between OCSes and ToRs
        for torId in xrange(1, self.numToRs + 1):
            torNodeId = ConvertToNodeId(torId, ToR, self.numHosts * self.numToRs, self.numToRs)
            for ocsId in xrange(1, self.numOCSes + 1):
                ocsNodeId = ConvertToNodeId(ocsId, OCS, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                self.Links[torNodeId, ocsNodeId] = Link((torNodeId, ocsNodeId), self.link_sh_Bw)
                self.Links[ocsNodeId, torNodeId] = Link((ocsNodeId, torNodeId), self.link_sh_Bw)
                # print torNodeId, coreNodeId

        # 4. Logically topology between ToRs and ToRs
        f = open(inDir + topoFileName, "r")
        ocsId = 0
        for line in f.readlines():
            l = line.split()
            if l[0] == 'ocs':
                ocsId = int(l[1])
                self.d_matches[ocsId] = []
                self.s_matches[ocsId] = []
            else:
                srcToRId = int(l[0])
                dstToRId = int(l[1])
                self.d_matches[ocsId].append((srcToRId, dstToRId))
                self.s_matches[ocsId].append((srcToRId, dstToRId))
                srcToRNodeId = ConvertToNodeId(srcToRId, ToR, self.numHosts * self.numToRs, self.numToRs)
                dstToRNodeId = ConvertToNodeId(dstToRId, ToR, self.numHosts * self.numToRs, self.numToRs)

                link_aggregation = False
                for pre_ocsId in xrange(1, ocsId):
                    if (srcToRId, dstToRId) in self.d_matches[pre_ocsId]:
                        pre_ocsNodeId = ConvertToNodeId(pre_ocsId, OCS, self.numHosts * self.numToRs, self.numToRs,
                                                        self.numCores)
                        # update the physically topology for link aggregation                         
                        self.Links[srcToRNodeId, pre_ocsNodeId].linkCap += self.link_sh_Bw
                        self.Links[pre_ocsNodeId, dstToRNodeId].linkCap += self.link_sh_Bw
                        self.Links[srcToRNodeId, pre_ocsNodeId].residualCap += self.link_sh_Bw
                        self.Links[pre_ocsNodeId, dstToRNodeId].residualCap += self.link_sh_Bw
                        link_aggregation = True
                        break

                if not link_aggregation:
                    self.com_network.add_edge(srcToRNodeId, dstToRNodeId, ocsId=ocsId)
        f.close()

        # 5. Inital the port status
        for torId in range(1, self.numToRs + 1):
            self.ucastToR[torId] = (range(1, self.numOCSes + 1), range(1, self.numOCSes + 1))
            self.ucastToRFully[torId] = (range(1, self.numOCSes + 1), range(1, self.numOCSes + 1))
        for portId in range(1, self.numOCSes + 1):
            self.ucastPort[portId] = (range(1, self.numToRs + 1), range(1, self.numToRs + 1))
            self.ucastPortFully[portId] = (range(1, self.numToRs + 1), range(1, self.numToRs + 1))

    def CalMultiPaths(self, network, routing_type, srcHostId, dstHostId):
        """
        Multiple paths routing
        @ topo
        @ routing_type :k_shotrest, shortest
        @ host srcHostId
        @ host dstHostId
        """
        if (srcHostId, dstHostId) not in self.pathLinkIdList:
            self.pathLinkIdList[srcHostId, dstHostId] = []
            if srcHostId == dstHostId:
                assert False
                return self.pathLinkIdList[srcHostId, dstHostId]
            srcToRId = GetToRId(srcHostId, self.numHosts)
            dstToRId = GetToRId(dstHostId, self.numHosts)
            srcToRNodeId = ConvertToNodeId(srcToRId, ToR, self.numHosts * self.numToRs, self.numToRs)
            dstToRNodeId = ConvertToNodeId(dstToRId, ToR, self.numHosts * self.numToRs, self.numToRs)

            # if src host and dst host are in the same parent ToR switch
            if srcToRId == dstToRId:
                self.pathLinkIdList[srcHostId, dstHostId].append([(srcHostId, srcToRNodeId), (srcToRNodeId, dstHostId)])
                return self.pathLinkIdList[srcHostId, dstHostId]
            else:
                multiPathes = []
                tmp_cutoff = 2
                if routing_type == Shortest:
                    while not multiPathes:
                        multiPathes = list(
                            nx.all_simple_paths(network, source=srcToRNodeId, target=dstToRNodeId, cutoff=tmp_cutoff))
                        tmp_cutoff += 1
                elif routing_type == K_Shortest:
                    while len(multiPathes) < self.k:
                        multiPathes = list(
                            nx.all_simple_paths(network, source=srcToRNodeId, target=dstToRNodeId, cutoff=tmp_cutoff))
                        tmp_cutoff += 1
                        if tmp_cutoff > 10 and multiPathes:
                            break

                for pathNodeIds in multiPathes:
                    pathLinkIds = [(srcHostId, pathNodeIds[0])]
                    for i in range(len(pathNodeIds) - 1):
                        srcNodeId = pathNodeIds[i]
                        dstNodeId = pathNodeIds[i + 1]
                        srcNodeRole = GetNodeRole(srcNodeId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                        dstNodeRole = GetNodeRole(dstNodeId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                        if srcNodeRole == ToR and dstNodeRole == ToR:
                            ocsId = network[srcNodeId][dstNodeId]['ocsId']
                            ocsNodeId = ConvertToNodeId(ocsId, OCS, self.numHosts * self.numToRs, self.numToRs,
                                                        self.numCores)
                            pathLinkIds.append((pathNodeIds[i], ocsNodeId))
                            pathLinkIds.append((ocsNodeId, pathNodeIds[i + 1]))
                        else:
                            pathLinkIds.append((pathNodeIds[i], pathNodeIds[i + 1]))

                    pathLinkIds.append((pathNodeIds[-1], dstHostId))
                    self.pathLinkIdList[srcHostId, dstHostId].append(pathLinkIds)
                    # print self.pathLinkIdList[srcHostId, dstHostId]

        return self.pathLinkIdList[srcHostId, dstHostId]

    def WeightedRouting(self, pathLinkIdList):
        '''
        Select the path with max-min residual bandwidth
        '''
        maxResidualBw = -1
        pathLinkIds = 0
        '''
        for tmp_pathLinkIds in pathLinkIdList:
            ResidualBw = self.link_ss_Bw*self.numCores + self.link_sh_Bw*self.numOCSes
            for linkId in tmp_pathLinkIds[1:-1]:
                if ResidualBw > self.Links[linkId].residualCap:
                    ResidualBw = self.Links[linkId].residualCap
            if ResidualBw > maxResidualBw:
                maxResidualBw = ResidualBw
                pathLinkIds = tmp_pathLinkIds
        '''
        index = random.randint(0, len(pathLinkIdList) - 1)
        pathLinkIds = pathLinkIdList[index]
        return pathLinkIds

    def DemandEstimation(self):
        '''
        Estimate the demand based on max-min fariness
        '''
        # print 'DemandEstimation'
        starttime = datetime.now()
        current_links = list(self.H2SLinks)
        current_flows = list(self.runningFlows)
        for flow in current_flows:
            if not flow.pathLinkIds:
                current_flows.remove(flow)

        residual_cap = {}
        residual_flowIds = {}
        flow_demand = {}
        for flow in current_flows:
            flow_demand[flow.flowId] = 0.0

        counter = 0
        for link_id in self.H2SLinks:
            link = self.H2SLinks[link_id]
            residual_cap[link_id] = link.linkCap
            residual_flowIds[link_id] = list(link.flowIds)
            counter += 1
            # print link_id, list(link.flowIds)
            # print counter

        while current_flows:  # multi iterations
            if not current_links:
                break
            # find bottleneck rate
            bottleneck_rate = link.linkCap
            linksToRemove = []
            for link_id in current_links:
                if len(residual_flowIds[link_id]) != 0:
                    if bottleneck_rate >= residual_cap[link_id] / len(residual_flowIds[link_id]):
                        bottleneck_rate = residual_cap[link_id] / len(residual_flowIds[link_id])
                else:
                    linksToRemove.append(link_id)

            # delete the empty links
            for link_id in linksToRemove:
                current_links.remove(link_id)

            bottleneck_rate = max([min([bottleneck_rate, link.linkCap]), 0.001])
            # update flow bandwidth
            for flowId in flow_demand:
                flow_demand[flowId] += bottleneck_rate
            # delete bottleneck links and update related flows
            linksToRemove = []
            for link_id in current_links:
                residual_cap[link_id] -= bottleneck_rate * len(residual_flowIds[link_id])
                if residual_cap[link_id] <= 1.0e-20:
                    linksToRemove.append(link_id)
                    flowIds = list(residual_flowIds[link_id])

                    for flow_id in flowIds:
                        flow = self.flowsDict[flow_id]

                        if isinstance(flow.endId, list):  # multicast flows
                            srcHost = flow.startId
                            srcToRId = GetToRId(srcHost, self.numHosts)
                            srcToRNodeId = ConvertToNodeId(srcToRId, ToR, self.numHosts * self.numToRs, self.numToRs)
                            residual_flowIds[(srcHost, srcToRNodeId)].remove(flow_id)

                            for dstHost in flow.endId:
                                dstToRId = GetToRId(dstHost, self.numHosts)
                                dstToRNodeId = ConvertToNodeId(dstToRId, ToR, self.numHosts * self.numToRs,
                                                               self.numToRs)
                                residual_flowIds[(dstToRNodeId, dstHost)].remove(flow_id)
                            current_flows.remove(flow)
                        else:
                            pathInLink = flow.pathLinkIds
                            residual_flowIds[pathInLink[0]].remove(flow_id)
                            residual_flowIds[pathInLink[-1]].remove(flow_id)
                            current_flows.remove(flow)
            # delete the bottleneck links
            for link_id in linksToRemove:
                current_links.remove(link_id)

        return flow_demand
        endtime = datetime.now()
        timediff = endtime - starttime
        # print "demand_estimation ended. Execution time: %s \n" %timediff

    def UpdateTopology(self, eventQueue, curTime, update_type='unicast'):
        # print 'ReconfigureNetwork'

        tf_graph = nx.Graph()
        bp_src = range(1, self.numToRs + 1)
        bp_dst = range(self.numToRs + 1, self.numToRs * 2 + 1)

        for src in bp_src:
            tf_graph.add_node(src, bipartite=0, degree=0)
        for dst in bp_dst:
            tf_graph.add_node(dst, bipartite=1, degree=0)

        # 1. Demand estimation max-min fariness
        flow_demand = self.DemandEstimation()
        sorted_flowIds = sorted(flow_demand, key=lambda x: flow_demand[x], reverse=True)
        # print 'sorted_flowIds', sorted_flowIds
        for flowId in sorted_flowIds:
            flow = self.flowsDict[flowId]
            if isinstance(flow.endId, int):
                srcToRId = GetToRId(flow.startId, self.numHosts)
                dstToRId = GetToRId(flow.endId, self.numHosts)
                if srcToRId != dstToRId:
                    if (srcToRId, dstToRId + self.numToRs) not in tf_graph.edges():
                        tf_graph.add_edge(srcToRId, dstToRId + self.numToRs,
                                          weight=flow_demand[flowId] / self.link_ss_Bw)
                    else:
                        tf_graph.edge[srcToRId][dstToRId + self.numToRs]['weight'] += flow_demand[
                                                                                          flowId] / self.link_ss_Bw
        # hotspot demand
        for (src, dst) in tf_graph.edges():
            if tf_graph.edge[src][dst]['weight'] <= self.numCores:
                tf_graph.remove_edge(src, dst)
            else:
                tf_graph.edge[src][dst]['weight'] -= self.numCores

        # 2. Calculate new topology (max-weight b-matching)
        if tf_graph.edges() or update_type == 'multicast':
            # print 'tf_graph.edges()', tf_graph.edges(data=True)
            ucastToR = copy.deepcopy(self.ucastToR)
            ucastPort = copy.deepcopy(self.ucastPort)

            cur_matches = {}
            while tf_graph.edges():
                match = nx.max_weight_matching(tf_graph, maxcardinality=False)
                # print len(match), match
                for src in match:
                    dst = match[src]
                    if src <= self.numToRs:
                        # print src, dst, tf_graph[src][dst]['weight']
                        maxPorts = list(set(ucastToR[src][0]) & set(ucastToR[dst - self.numToRs][1]))
                        if maxPorts:
                            traffic_weight = get_weight(tf_graph[src][dst]['weight'])
                            port_nums = min(traffic_weight, len(maxPorts))

                            for i in xrange(0, port_nums):
                                portId = maxPorts[i]
                                ucastToR[src][0].remove(portId)
                                ucastToR[dst - self.numToRs][1].remove(portId)
                                ucastPort[portId][0].remove(src)
                                ucastPort[portId][1].remove(dst - self.numToRs)
                                if portId not in cur_matches:
                                    cur_matches[portId] = [(src, dst - self.numToRs)]
                                else:
                                    cur_matches[portId].append((src, dst - self.numToRs))
                        tf_graph.remove_edge(src, dst)

            # 3. Augmenting to k-regular graph
            for portId in cur_matches:
                for (src, dst) in self.d_matches[portId]:
                    if src in ucastPort[portId][0] and dst in ucastPort[portId][1]:
                        cur_matches[portId].append((src, dst))
                        # print 'portId' ,portId, src, dst
                        ucastPort[portId][0].remove(src)
                        ucastPort[portId][1].remove(dst)

            for portId in cur_matches:
                for dst in ucastPort[portId][1]:
                    match_src = 0
                    for src in ucastPort[portId][0]:
                        if src != dst:
                            match_src = src
                            break
                    if match_src:
                        cur_matches[portId].append((src, dst))
                        ucastPort[portId][0].remove(match_src)
                    else:  # last element and src == dst
                        (src1, dst1) = cur_matches[portId].pop()
                        cur_matches[portId].append((src1, ucastPort[portId][1][0]))
                        cur_matches[portId].append((src, dst1))

            if update_type == 'multicast':
                for portId in self.ucastPort:
                    # print 'portId',portId
                    match = list(self.d_matches[portId])
                    # print self.ucastPort[portId][0]
                    # print self.ucastPort[portId][1]
                    for (src, dst) in match:
                        if src not in self.ucastPort[portId][0] or dst not in self.ucastPort[portId][1]:
                            self.d_matches[portId].remove((src, dst))
                            self.s_matches[portId].remove((src, dst))

                            # print 'd_matches', self.d_matches

            for portId in self.d_matches:
                if portId in cur_matches:
                    self.s_matches[portId] = list(sorted(list(set(cur_matches[portId]) & set(self.d_matches[portId]))))
                    self.d_matches[portId] = list(sorted(cur_matches[portId]))
                else:
                    self.s_matches[portId] = list(self.d_matches[portId])

        # print 'self.d_matches', self.d_matches
        # print 'self.s_matches', self.s_matches

        if update_type == 'multicast' or self.d_matches != self.s_matches:
            self.Update_network(self.s_matches)
            self.UpdateFlow(0, UpdateTopology, eventQueue, curTime)

            event = LinkAdjustedEvent(curTime + self.adjust_delay)
            self.LinkAdjustedEvent = event
            self.UpdateTopologyEvent = 0
            eventQueue.push(event, event.time)

        else:
            event = UpdateTopologyEvent(curTime + self.interval)
            self.UpdateTopologyEvent = event
            self.LinkAdjustedEvent = 0
            eventQueue.push(event, event.time)

    def UpdateTopologyFinished(self, eventQueue, curTime):
        # print 'UpdateNetworkFinished'
        self.Update_network(self.d_matches)
        self.s_matches = copy.deepcopy(self.d_matches)
        self.UpdateFlow(0, UpdatedTopology, eventQueue, curTime)

        event = UpdateTopologyEvent(curTime + self.interval)
        self.UpdateTopologyEvent = event
        self.LinkAdjustedEvent = 0
        eventQueue.push(event, event.time)

    def Update_network(self, matches):
        # 1. initial the links, com_network and pathLinkIdList
        self.pathLinkIdList = {}  # clear the routing

        for linkId in self.Links:  # clear the flows
            self.Links[linkId].flowIds = []

        for torId in xrange(1, self.numToRs + 1):
            torNodeId = ConvertToNodeId(torId, ToR, self.numHosts * self.numToRs, self.numToRs)
            for ocsId in xrange(1, self.numOCSes + 1):
                ocsNodeId = ConvertToNodeId(ocsId, OCS, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                self.Links[torNodeId, ocsNodeId].linkCap = self.link_sh_Bw
                self.Links[ocsNodeId, torNodeId].linkCap = self.link_sh_Bw

        # 2. Logically topology between ToRs and ToRs
        self.com_network = nx.DiGraph()
        for torId in xrange(1, self.numToRs + 1):
            torNodeId = ConvertToNodeId(torId, ToR, self.numHosts * self.numToRs, self.numToRs)
            for coreId in xrange(1, self.numCores + 1):
                coreNodeId = ConvertToNodeId(coreId, Core, self.numHosts * self.numToRs, self.numToRs)
                self.com_network.add_edge(torNodeId, coreNodeId)
                self.com_network.add_edge(coreNodeId, torNodeId)

        for ocsId in matches:
            for (srcToRId, dstToRId) in matches[ocsId]:
                srcToRNodeId = ConvertToNodeId(srcToRId, ToR, self.numHosts * self.numToRs, self.numToRs)
                dstToRNodeId = ConvertToNodeId(dstToRId, ToR, self.numHosts * self.numToRs, self.numToRs)

                link_aggregation = False
                for pre_ocsId in xrange(1, ocsId):
                    if (srcToRId, dstToRId) in matches[pre_ocsId]:
                        pre_ocsNodeId = ConvertToNodeId(pre_ocsId, OCS, self.numHosts * self.numToRs, self.numToRs,
                                                        self.numCores)
                        # update the physically topology for link aggregation                         
                        self.Links[srcToRNodeId, pre_ocsNodeId].linkCap += self.link_sh_Bw
                        self.Links[pre_ocsNodeId, dstToRNodeId].linkCap += self.link_sh_Bw
                        self.Links[srcToRNodeId, pre_ocsNodeId].residualCap += self.link_sh_Bw
                        self.Links[pre_ocsNodeId, dstToRNodeId].residualCap += self.link_sh_Bw
                        link_aggregation = True
                        break

                if not link_aggregation:
                    self.com_network.add_edge(srcToRNodeId, dstToRNodeId, ocsId=ocsId)

    def UpdateFlow(self, curFlow, eventType, eventQueue, curTime):
        """
        Fairness bandwidth allocation
        Find related flows and update their flowBw, transTime, endTime.
        """
        if eventType == FlowArrival:
            # update links and running flows
            curFlow.updateTime = curTime
            self.runningFlows.append(curFlow)
            self.flowsDict[curFlow.flowId] = curFlow
            self.runningFlowsDict[curFlow.flowId] = curFlow

            # flow arrival, calculating routes
            if isinstance(curFlow.endId, int):  # unicast flow arrival
                pathLinkIdList = self.CalMultiPaths(self.com_network, K_Shortest, curFlow.startId, curFlow.endId)
                curFlow.pathLinkIds = self.WeightedRouting(pathLinkIdList)
                curFlow.pathLength = len(curFlow.pathLinkIds)

                pathInLink = curFlow.pathLinkIds
                for link_id in pathInLink:
                    link = self.Links[link_id]
                    if curFlow.flowId not in link.flowIds:
                        link.flowIds.append(curFlow.flowId)
            else:  # multicast flow arrival
                self.MulticastFlowArrival(curFlow, curTime, eventQueue)  # multicast flow arrival
                if self.type != 'EPS':
                    return

        elif eventType == FlowFinished:
            # update energy
            for flow in self.runningFlows:  # update the energy before changing routes
                pathInLink = flow.pathLinkIds
                energy = 0
                for (srcId, dstId) in pathInLink:
                    # print srcId, dstId
                    srcNodeRole = GetNodeRole(srcId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                    dstNodeRole = GetNodeRole(dstId, self.numHosts * self.numToRs, self.numToRs, self.numCores)

                    if srcNodeRole == Host and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Core:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == OCS:
                        energy += PortPower + OCSPower
                    elif srcNodeRole == Core and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == OCS and dstNodeRole == ToR:
                        energy += PortPower + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Host:
                        energy += PortPower * 2
                flow.energy += energy * flow.bw * (curTime - flow.updateTime)
                flow.remainSize -= flow.bw * (curTime - flow.updateTime)
                flow.remainTime -= curTime - flow.updateTime
                flow.updateTime = curTime
                flow.bw = 0.0

            curFlow.finishTime = curTime
            pathInLink = curFlow.pathLinkIds
            for (srcId, dstId) in pathInLink:
                link = self.Links[(srcId, dstId)]
                link.flowIds.remove(curFlow.flowId)

            self.runningFlows.remove(curFlow)
            self.finishedFlows.append(curFlow)
            self.runningFlowsDict.pop(curFlow.flowId)
            self.flowsDict.pop(curFlow.flowId)

            if len(self.finishedFlows) % 100 == 0:
                print len(self.finishedFlows)

            mflowId = curFlow.mcastFlowId
            if mflowId != 0:
                self.UpdateMulticast(mflowId, curFlow, curTime, eventQueue)

        elif eventType == UpdateTopology:
            # print 'UpdateTopology'
            for flow in self.runningFlows:
                pathInLink = []
                # update the energy before changing routes
                pathInLink = flow.pathLinkIds
                energy = 0
                for (srcId, dstId) in pathInLink:
                    # print srcId, dstId
                    srcNodeRole = GetNodeRole(srcId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                    dstNodeRole = GetNodeRole(dstId, self.numHosts * self.numToRs, self.numToRs, self.numCores)

                    if srcNodeRole == Host and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Core:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == OCS:
                        energy += PortPower + OCSPower
                    elif srcNodeRole == Core and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == OCS and dstNodeRole == ToR:
                        energy += PortPower + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Host:
                        energy += PortPower * 2
                flow.energy += energy * flow.bw * (curTime - flow.updateTime)
                flow.remainSize -= flow.bw * (curTime - flow.updateTime)
                flow.remainTime -= curTime - flow.updateTime
                flow.updateTime = curTime
                flow.bw = 0.0

                if isinstance(flow.endId, int):  # unicast flows recalculate routes
                    # update routes
                    pathLinkIdList = self.CalMultiPaths(self.com_network, K_Shortest, flow.startId, flow.endId)
                    flow.pathLinkIds = self.WeightedRouting(pathLinkIdList)
                    flow.pathLength = len(flow.pathLinkIds)

                pathInLink = flow.pathLinkIds
                for linkId in pathInLink:
                    link = self.Links[linkId]
                    if flow.flowId not in link.flowIds:
                        link.flowIds.append(flow.flowId)

        elif eventType == UpdatedTopology:  # update topology finished
            # print 'UpdatedTopology!!!'
            for flow in self.runningFlows:
                pathInLink = flow.pathLinkIds
                energy = 0
                for (srcId, dstId) in pathInLink:
                    # print srcId, dstId
                    srcNodeRole = GetNodeRole(srcId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                    dstNodeRole = GetNodeRole(dstId, self.numHosts * self.numToRs, self.numToRs, self.numCores)

                    if srcNodeRole == Host and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Core:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == OCS:
                        energy += PortPower + OCSPower
                    elif srcNodeRole == Core and dstNodeRole == ToR:
                        energy += PortPower * 2 + EPSPower
                    elif srcNodeRole == OCS and dstNodeRole == ToR:
                        energy += PortPower + EPSPower
                    elif srcNodeRole == ToR and dstNodeRole == Host:
                        energy += PortPower * 2

                flow.energy += energy * flow.bw * (curTime - flow.updateTime)
                flow.remainSize -= flow.bw * (curTime - flow.updateTime)
                flow.remainTime -= curTime - flow.updateTime
                flow.updateTime = curTime
                flow.bw = 0.0

                if isinstance(flow.endId, int):  # unicast flows
                    pathLinkIdList = self.CalMultiPaths(self.com_network, K_Shortest, flow.startId, flow.endId)
                    flow.pathLinkIds = self.WeightedRouting(pathLinkIdList)
                    flow.pathLength = len(flow.pathLinkIds)
                else:  # multicast flows
                    if flow.ocsPathLinkIds:
                        flow.pathLinkIds = list(flow.ocsPathLinkIds)
                        flow.ocsPathLinkIds = []
                        flow.pathLength = 3

                pathInLink = flow.pathLinkIds
                for linkId in pathInLink:
                    link = self.Links[linkId]
                    if flow.flowId not in link.flowIds:
                        link.flowIds.append(flow.flowId)

        # -------------------------------------------------------------
        current_links = list(self.Links)
        current_flows = list(self.runningFlows)
        for flow in self.runningFlows:
            if not flow.pathLinkIds:
                current_flows.remove(flow)

        residual_cap = {}
        residual_flowIds = {}
        for link_id in self.Links:
            link = self.Links[link_id]
            residual_cap[link_id] = link.linkCap
            residual_flowIds[link_id] = list(link.flowIds)
            self.Links[link_id].residualCap = link.linkCap

        for flow in self.runningFlows:
            # calculate energy
            pathInLink = flow.pathLinkIds
            energy = 0
            for (srcId, dstId) in pathInLink:
                srcNodeRole = GetNodeRole(srcId, self.numHosts * self.numToRs, self.numToRs, self.numCores)
                dstNodeRole = GetNodeRole(dstId, self.numHosts * self.numToRs, self.numToRs, self.numCores)

                if srcNodeRole == Host and dstNodeRole == ToR:
                    energy += PortPower * 2 + EPSPower
                elif srcNodeRole == ToR and dstNodeRole == Core:
                    energy += PortPower * 2 + EPSPower
                elif srcNodeRole == ToR and dstNodeRole == OCS:
                    energy += PortPower + OCSPower
                elif srcNodeRole == Core and dstNodeRole == ToR:
                    energy += PortPower * 2 + EPSPower
                elif srcNodeRole == OCS and dstNodeRole == ToR:
                    energy += PortPower + EPSPower
                elif srcNodeRole == ToR and dstNodeRole == Host:
                    energy += PortPower * 2
            flow.energy += energy * flow.bw * (curTime - flow.updateTime)
            # update flow status
            flow.remainSize -= flow.bw * (curTime - flow.updateTime)
            flow.remainTime -= curTime - flow.updateTime
            flow.updateTime = curTime
            flow.bw = 0.0
            # update flow and eventQueue
            if flow.finishEvent != 0:
                flow.finishEvent.cancelled = True

        while current_flows:  # multi iterations
            if not current_links:
                break
            bottleneck_rate = link.linkCap
            linksToRemove = []
            for link_id in current_links:
                if len(residual_flowIds[link_id]):
                    if bottleneck_rate >= residual_cap[link_id] / len(residual_flowIds[link_id]):
                        bottleneck_rate = residual_cap[link_id] / len(residual_flowIds[link_id])
                else:
                    linksToRemove.append(link_id)

            # delete the empty links
            for link_id in linksToRemove:
                current_links.remove(link_id)

            bottleneck_rate = max([min([bottleneck_rate, link.linkCap]), 0.001])
            # update flow bandwidth
            for flow in current_flows:
                if flow.pathLinkIds:
                    flow.bw += bottleneck_rate

            # update related flows
            linksToRemove = []
            for link_id in current_links:
                residual_cap[link_id] -= bottleneck_rate * len(residual_flowIds[link_id])
                self.Links[link_id].residualCap = residual_cap[link_id]

                if residual_cap[link_id] <= 1.0e-20:
                    linksToRemove.append(link_id)
                    flowIds = list(residual_flowIds[link_id])

                    for flow_id in flowIds:
                        flow = self.runningFlowsDict[flow_id]
                        pathInLink = flow.pathLinkIds
                        for flow_link_id in pathInLink:
                            residual_flowIds[flow_link_id].remove(flow_id)
                        current_flows.remove(flow)
                        # update the flow status
                        flow.finishTime = curTime + flow.remainSize / flow.bw + PROPAGATION_DELAY * flow.pathLength
                        event = FlowFinishedEvent(flow.finishTime, flow)
                        flow.finishEvent = event
                        eventQueue.push(event, event.time)
            # delete the bottleneck links
            for link_id in linksToRemove:
                current_links.remove(link_id)

        del current_flows
        del current_links
        del residual_cap
        del residual_flowIds

    def AssignMulticast(self):
        f = open(inDir + self.mflowsFileName, "r")
        for line in f.readlines():
            l = line.split()
            if l[0] == 'flowsNum:':
                startTime = float(l[3])
            else:
                flowId = int(l[0])
                mcastFlow = MulticastFlow()
                mcastFlow.flowId = flowId
                mcastFlow.flowSize = float(l[1]) * 8  # bit
                mcastFlow.startTime = startTime
                mcastFlow.srcToR = int(re.split(':|,', l[2])[0])
                mcastFlow.srcHost = (mcastFlow.srcToR - 1) * self.numHosts + int(re.split(':|,', l[2])[1])
                # print mcastFlow.srcToR, mcastFlow.srcHost

                # print "time", mcastFlow.flowSize/self.link_sh_Bw
                for i in xrange(3, len(l)):
                    dstToR = int(re.split(':|,', l[i])[0])
                    mcastFlow.dstToRs[dstToR] = []
                    for j in xrange(1, len(re.split(':|,', l[i]))):
                        dstHost = (dstToR - 1) * self.numHosts + int(re.split(':|,', l[i])[j])
                        mcastFlow.dstToRs[dstToR].append(dstHost)
                        mcastFlow.dstHosts[dstHost] = False
                        # print dstToR, mcastFlow.dstToRs[dstToR]
                mcastFlow.groupSize = len(mcastFlow.dstHosts)
                self.mcastFlows[flowId] = mcastFlow
        f.close()

    def InitialMulticast(self, eventQueue):
        pass

    def MulticastFlowArrival(self, curFlow, curTime, eventQueue):
        pass

    def UpdateMulticast(self, mflowId, curFlow, curTime, eventQueue):
        pass

    def PrintFlows(self):
        """
        print finishedFlows
        """
        # print mulitcast flows
        fileDir = self.mflowsFileName.split('/')
        fileName = self.mflowsFileName.split('.')
        if not os.path.exists(outDir + fileDir[0]) and len(fileDir) >= 2:
            os.makedirs(outDir + fileDir[0])
        f_name = outDir + fileName[0] + '_' + self.type + '_%s' % self.update_enable + '_%s' % self.workload + '.txt'

        overall_fct = 0.0
        overall_avg_fct = 0.0
        f = open(f_name, "w")
        for flow in self.mcastFlows.values():
            flowTransTime = flow.finishTime - flow.startTime
            overall_fct += flowTransTime
            if flowTransTime != 0:
                flow.bw = flow.flowSize / flowTransTime
                print >> f, "flowId: %d\t flowSize: %d\t fct: %f\t %f\t %f\t bw %f\t energy: %s" % (
                    flow.flowId, flow.flowSize, flowTransTime, flow.startTime, flow.finishTime, flow.bw, flow.energy)
        f.close()
        overall_avg_fct = overall_fct / len(self.mcastFlows.values())
        print 'mulitcast flows:', overall_fct, overall_avg_fct

        # print unicast flows
        fileDir = self.uflowsFileName.split('/')
        fileName = self.uflowsFileName.split('.')
        if not os.path.exists(outDir + fileDir[0]) and len(fileDir) >= 2:
            os.makedirs(outDir + fileDir[0])
        f_name = outDir + fileName[0] + '_' + self.type + '_%s' % self.update_enable + '_%s' % self.workload + '.txt'

        overall_fct = 0.0
        overall_avg_fct = 0.0
        unicastFlowLen = 0
        f = open(f_name, "w")
        for flow in self.flows:
            if flow.mcastFlowId == 0:
                unicastFlowLen += 1
                flowTransTime = flow.finishTime - flow.startTime
                overall_fct += flowTransTime
                if flowTransTime != 0:
                    flow.bw = flow.flowSize / flowTransTime
                    print >> f, "flowId: %d\t flowSize: %d\t fct: %f\t %f\t %f\t bw %f\t energy: %s" % (
                        flow.flowId, flow.flowSize, flowTransTime, flow.startTime, flow.finishTime, flow.bw,
                        flow.energy)
        f.close()
        if unicastFlowLen:
            overall_avg_fct = overall_fct / unicastFlowLen
        print 'unicast flows:', overall_fct, overall_avg_fct
